import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:三数之和
 * User: bjc
 * Date: 2025-11-06
 * Time: 16:55
 */
public class Test07_threeSum {
    public static List<List<Integer>> threeSum1(int[] nums){
        //1.先对数组进行排序
        Arrays.sort(nums);
        //2.使用双指针解决
        List<List<Integer>> result = new ArrayList<>();
        for(int i = 0;i < nums.length - 2;i++){
            //因为是从小到大排序，所以第一个如果大于0，则直接跳出循环
            if(nums[i] > 0) break;

            int left = i+1,right = nums.length-1;
            while(left < right){
                int sum = nums[i]+nums[left]+nums[right];
                if(sum > 0) right--;
                else if(sum < 0) left++;
                else {
                    result.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    left++;
                    right--;
                    //去重
                    while(left < right && nums[left] == nums[left-1]) left++;
                    while(left < right && nums[right] == nums[right+1]) right--;

                }
            }
            //去重
            while(i < nums.length - 1 && nums[i] == nums[i+1]) i++;
        }
        return result;

    }

    public static List<List<Integer>> threeSum(int[] nums) {
        //1.先把数组排序
        Arrays.sort(nums);
        //2.使用双指针解决
        List<List<Integer>> result = new ArrayList<>();
        for(int i = nums.length - 1;i >= 2;i--){
            //外层去重，跳过相同的值
            if(i < nums.length - 1 && nums[i] == nums[i+1]) continue;
            int j = 0,k = i-1;
            while(j < k){
                int sum = nums[j]+nums[k]+nums[i];
                if(sum > 0) k--;
                else if(sum < 0) j++;
                else{
                    /*List<Integer> list = new ArrayList<>();
                    list.add(nums[j]);
                    list.add(nums[k]);
                    list.add(nums[i]);*/
                    //使用Arrays工具类中的asList方法
                    result.add(Arrays.asList(nums[j],nums[k],nums[i]));
                    j++;
                    k--;
                    //去重
                    while(j < k && nums[j] == nums[j+1]) j++;
                    while(j < k && nums[k] == nums[k-1]) k--;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        System.out.println(threeSum1(nums));
        System.out.println(threeSum(nums));

    }
}
